
//923.三数之和的多种可能
class Solution {
public:
    int threeSumMulti(vector<int>& nums, int target) {
        //三数求和变形题
        unordered_map<int,int> mm;
        for(auto e:nums) mm[e]++;  //记录每个数据的个数

        int n=nums.size();
        sort(nums.begin(),nums.end());
        int ret=0;
        for(int i=0;i<n;i++)  //遍历数组
        {
            //进行两数求和
            if(--mm[nums[i]]==0) mm.erase(mm[nums[i]]);
            int left=i+1,right=n-1;
            while(left<right)
            {
                if(nums[left]+nums[right]+nums[i]>target) right--;
                else if(nums[left]+nums[right]+nums[i]<target) left++;
                else
                {
                    //防止left与right的值相等造成的重复计数
                    if(nums[left]==nums[right]) ret=(ret+(mm[nums[right]]-1)*mm[nums[right]]/2)%1000000007;  
                    else ret=(ret+mm[nums[right]]*mm[nums[left]])%1000000007;
                    
                    right--,left++;
                    while(left<right&&nums[left]==nums[left-1]) left++;   //取出重复元素
                    while(left<right&&nums[right]==nums[right+1]) right--;   //取出重复元素
                }
            }
        }
        return ret;
    }
};